#-*- coding: utf-8 -*-
from Node import *
from copy import copy

class ListeChainee(object):
    """
    Classe permettant la gestion de listes chainées.
    Lors de l'ajout d'un élément, une copie sera faite 
    si c'est un objet ListeChainee mais pas si c'est un Node.

    TODO    check tail/size consistency via check() 
                after insert*(), r?add, r?mul, remove*
    """

    def __init__(self, *args):
        """
        >>> print ListeChainee()
        []
        >>> print ListeChainee('booh')
        ['booh']
        >>> print ListeChainee(1, 2)
        [1, 2]
        >>> print ListeChainee('answer', 42)
        ['answer', 42]
        """
        self.head = self.tail = None
        self.size = 0
        if len(args)==1 and args[0]==None:
            return #liste vide
        else:
            for x in args:
                self.insertEnd(x)

    def insertEnd(self, n):
        """
        Insère un élément ou une autre liste à la fin.
        >>> x = ListeChainee(1, 2)
        >>> x.insertEnd(3)
        >>> print x
        [1, 2, 3]
        >>> x = ListeChainee(1)
        >>> x.insertEnd(Node(2, Node(3)))
        >>> print x
        [1, 2, 3]
        >>> x = ListeChainee(1)
        >>> y = ListeChainee(2)
        >>> x.insertEnd(y)
        >>> print x
        [1, 2]
        >>> x = ListeChainee()
        >>> x.insertEnd(Node(1, Node(2)))
        >>> print x
        [1, 2]
        """
        if isinstance(n, ListeChainee):
            cp = copy(n)
            if self.tail!=None:
                self.tail.next = cp.head
            else:
                self.head = cp.head
            self.tail = cp.tail
            self.size += n.size
        elif isinstance(n, Node):
            if self.tail!=None:
                self.tail.next = n
                self.tail = n.getTail()
                self.size += n.getSize()
            else:
                self.head = n
                self.tail = n.getTail()
                self.size = n.getSize()
        else:
            #on crée un nouveau noeud, que la liste soit vide ou non.
            nw = Node(n)
            if self.head==None:
                #soit en n'avait pas encore,
                #on fait tout pointer vers lui
                self.head = self.tail = nw
            else:
                #soit on en a déjà,
                #on en crée un et on fait
                #pointer le dernier vers lui
                self.tail.next = nw
                self.tail = nw
            #on incrémente le compteur...
            self.size += 1

    def insertBeginning(self, n):
        """
        Insère un élément ou une autre liste au début.
        >>> x = ListeChainee(2)
        >>> x.insertBeginning(1)
        >>> print x
        [1, 2]
        """
        if isinstance(n, ListeChainee):
            cp = copy(n)
            cp.tail.next = self.head
            self.head = cp.head
            self.size += cp.size
        elif isinstance(n, Node):
            self.size += n.getSize()
            n.getTail().next = self.head
            self.head = n
        else:
            nw = Node(n, self.head)
            if self.head==None:
                #liste vide
                self.head = self.tail = nw
            else:
                #liste non vide
                self.head = nw

    def __len__(self):
        """
        >>> print len(ListeChainee(1, 2, 3))
        3
        """
        return self.size

    def __str__(self):
        """
        Retourne les éléments sous la forme [a, b]
        >>> print ListeChainee()
        []
        >>> print ListeChainee('booh')
        ['booh']
        >>> print ListeChainee(1, 2)
        [1, 2]
        >>> print ListeChainee('answer', 42)
        ['answer', 42]
        """
        s = ""
        p = self.head
        while p:
            s += repr(p.data) + ", "
            p = p.next
        return "[" + s[:-2] + "]"

    def __repr__(self):
        """
        Retourne la représentation de la liste chainée utilisée en interne.
        >>> ListeChainee()
        *
        >>> ListeChainee(1, 2)
        1 -> 2 -> *
        """
        return Node.repr_s(self.head)

    def insert(self, i, n):
        """
        Insère un élément ou une autre liste n à l'indice i. 
        Complexité dans le pire des cas : O(i)
        >>> x = ListeChainee(0, 1, 2, 3)
        >>> x.insert(1, 42)
        >>> print x
        [0, 42, 1, 2, 3]
        >>> x = ListeChainee(1, 2)
        >>> x.insert(3, 42)
        Traceback (most recent call last):
        ...
        IndexError: list index out of range
        >>> x = ListeChainee(1, 2)
        >>> x.insert(1, Node(2, Node(3)))
        >>> print x
        [1, 2, 2, 3]
        """
        p = self.head
        #cas tordus à éliminer
        if i==0:
            return self.insertBeginning(n)
        elif i==self.size-1:
            return self.insertEnd(n)
        #on va skipper i éléments (si possible)
        while i:
            if p == None:
                raise IndexError("list index out of range")
            prev = p
            p = p.next
            i -= 1
        #on insère normalement...
        if isinstance(n, ListeChainee):
            nv = copy(n)
            self.ct += nv.size
            prev.next = nv.head
            nv.tail.next = p
        elif isinstance(n, Node):
            prev.next = n
            self.ct += n.getSize()
            n.getTail().next = p
        else:
            nv = Node(n, p)
            prev.next = nv
            self.size += 1

    def seek(self, i):
        """
        Récupère le noeud correspondant au ième élément. 
        Complexité dans le pire des cas : O(i).
        >>> ListeChainee(1, 2).seek(1)
        2 -> *
        """
        p = self.head
        #on va skipper i éléments (si possible)
        while i:
            if p == None:
                raise IndexError("list index out of range")
            p = p.next
            i -= 1
        return p

    def __getitem__(self, i):
        """
        Complexité dans le pire des cas : O(i)
        >>> ListeChainee(1, 2)[1]
        2
        >>> ListeChainee(1)[1]
        Traceback (most recent call last):
        ...
        IndexError: list index out of range
        """
        n = self.seek(i)
        if n==None:
            raise IndexError("list index out of range")
        else:
            return n.data

    def __setitem__(self, i, d):
        """
        Complexité dans le pire des cas : O(i).
        Ne fonctionnera pas si d est autre chose qu'un immuable.
        >>> x = ListeChainee(1, 2)
        >>> x[1] = 3
        >>> print x
        [1, 3]
        >>> x = ListeChainee(1, 2)
        >>> x[2] = 3
        Traceback (most recent call last):
        ...
        IndexError: list index out of range
        """
        n = self.seek(i)
        if n == None:
            raise IndexError("list index out of range")
        else:
            n.data = d
	
    def removeBeginning(self):
        """
        Supprime le premier élément de la liste.
        >>> x = ListeChainee(1, 2)
        >>> y = x.removeBeginning()
        >>> print x
        [2]
        >>> x = ListeChainee()
        >>> x.removeBeginning()
        Traceback (most recent call last):
        ...
        IndexError: empty list!
        """
        if self.head==None:
            raise IndexError("empty list!")
        v = self.head.data
        self.head = self.head.next
        self.size -= 1
        return v

    def removeEnd(self):
        """
        Supprime le dernier élément de la liste. 
        Complexité dans le pire des cas : O(n).
        >>> x = ListeChainee(1, 2)
        >>> y = x.removeEnd()
        >>> print x
        [1]
        >>> x = ListeChainee()
        >>> x.removeEnd()
        Traceback (most recent call last):
        ...
        IndexError: empty list!
        """
        if self.head==None:
            raise IndexError("empty list!")
        v = self.tail.data
        p = self.head
        while p.next:
            prev = p
            p = p.next
        self.tail = prev
        self.tail.next = None #BUGFIX
        self.size -= 1
        return v

    def remove(self, i):
        """
        Supprime le ième élément de la liste.
        Complexité dans le pire des cas : O(i).
        >>> x = ListeChainee(1, 2, 3)
        >>> y = x.remove(1)
        >>> print x
        [1, 3]
        >>> x = ListeChainee()
        >>> x.remove(1)
        Traceback (most recent call last):
        ...
        IndexError: list index out of range
        """
        #cas spéciaux à écarter
        if i==0:
            return self.removeBeginning()
        elif i==self.size-1:
            return self.removeEnd()
        #on va skipper i éléments (si possible)
        p = self.head
        while i:
            if p == None:
                raise IndexError("list index out of range")
            prev = p
            p = p.next
            i -= 1
        #p pointe vers l'élément à supprimer,
        #prev sur son précédent.
        prev.next = p.next
        self.size -= 1
        return p.data

    def isEmpty(self):
        """
        >>> print ListeChainee(1).isEmpty()
        False
        >>> print ListeChainee().isEmpty()
        True
        """
        return self.size == 0
	
    def clear(self):
        """
        >>> x = ListeChainee(1)
        >>> x.clear()
        >>> print x
        []
        """
        self.head = self.tail = None
        self.size = 0
	
    def __copy__(self):
        """
        >>> print copy(ListeChainee(1, 2))
        [1, 2]
        """
        nw = ListeChainee()
        p = self.head
        while p:
            nw.insertEnd(p.data)
            p = p.next
        return nw

    def __add__(self, other):
        """
        >>> print ListeChainee(1, 2) + ListeChainee(3, 4)
        [1, 2, 3, 4]
        >>> print ListeChainee(1, 2) + 3
        [1, 2, 3]
        """
        if other==None:
            return copy(self)
        elif isinstance(other, ListeChainee) or isinstance(other, Node):
            ret = copy(self)
            ret.insertEnd(other)
            return ret
        else:
            a = copy(self)
            b = Node(other)
            a.tail.next = b
            a.tail = b
            a.size += 1
            return a

    def __radd__(self, other):
        """
        >>> print ListeChainee(1, 2) + ListeChainee(3, 4)
        [1, 2, 3, 4]
        >>> print 3 + ListeChainee(1, 2)
        [3, 1, 2]
        """
        if other==None:
            return copy(self)
        elif isinstance(other, ListeChainee) or isinstance(other, Node):
            ret = copy(self)
            ret.insertBeginning(other)
            return ret
        else:
            b = copy(self)
            a = Node(other)
            a.next = b.head
            b.size += 1
            b.head = a
            return b

    def __contains__(self, d):
        """
        >>> print 1 in ListeChainee(3, 2, 1)
        True
        >>> print 42 in ListeChainee(1, 3, 5, 7)
        False
        >>> print ListeChainee(31, 2) in ListeChainee(1, 2, 3, 4)
        False
        >>> print ListeChainee(1, 2) in ListeChainee(1, 2, 3, 4)
        True
        >>> print ListeChainee(1) in ListeChainee(1, 2, 3, 4)
        True
        >>> print ListeChainee(4) in ListeChainee(1, 2, 3, 4)
        True
        >>> print ListeChainee() in ListeChainee(1)
        True
        """
        p = self.head #on travaillera avec des noeuds
        if isinstance(d, ListeChainee):
            dp = d.head
            if dp==None:
                #l'ensemble vide est inclus à tous les ensembles
                return True
            while p:
                if p.data == dp.data:
                    dp = dp.next #on continue de comparer
                    if dp==None:
                        return True #terminé !
                else:
                    dp = d.head #on recommence depuis le début
                p = p.next
            return False #pas trouvé (pas entièrement, en tout cas)
        else:
            #simple recherche linéaire
            while p:
                if p.data == d:
                    return True
                p = p.next
            return False
    
    def __mul__(self, n):
        """
        >>> print ListeChainee(0, 1) * 3
        [0, 1, 0, 1, 0, 1]
        >>> print ListeChainee(1) * 4.2
        Traceback (most recent call last):
        ...
        TypeError: can't copy a list 4.2 times!
        """
        if not isinstance(n, int):
            raise TypeError("can't copy a list "+repr(n)+" times!")
        #théoriquement, on pourrait additionner à chaque fois,
        #mais ça générera trop de copies inutiles...
        res = copy(self)
        while n-1:
            cp = copy(self)
            res.tail.next = cp.head
            res.tail = cp.tail
            n -= 1
        res.size *= n
        return res

    def __rmul__(self, n):
        """
        >>> print 3 * ListeChainee(0, 1)
        [0, 1, 0, 1, 0, 1]
        >>> print 4.2 * ListeChainee(1)
        Traceback (most recent call last):
        ...
        TypeError: can't copy a list 4.2 times!
        """
        return self * n

    def check(self):
        """
        Vérifie la cohérence d'une liste chainée (longueur et fin).
        Codes d'erreurs : 0=ok, 1=fin, 2=taille
        >>> a = ListeChainee()
        >>> a.tail = 1
        >>> print a.check()
        1
        >>> a = ListeChainee()
        >>> print a.check()
        0
        >>> a = ListeChainee(2, 3)
        >>> a.size = 30
        >>> print a.check()
        2
        >>> a = ListeChainee(1, 2)
        >>> print a.check()
        0
        """
        if self.tail!=Node.getTail_s(self.head):
            return 1 #invalid tail
        elif self.size!=Node.getSize_s(self.head):
            return 2 #invalid size
        else:
            return 0 #ok


if __name__=='__main__':
    import doctest
    doctest.testmod()
